//有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 
//
// 
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 
//和 "192.168@1.1" 是 无效 IP 地址。 
// 
//
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序
//或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
// 
//
// 示例 2： 
//
// 
//输入：s = "0000"
//输出：["0.0.0.0"]
// 
//
// 示例 3： 
//
// 
//输入：s = "1111"
//输出：["1.1.1.1"]
// 
//
// 示例 4： 
//
// 
//输入：s = "010010"
//输出：["0.10.0.10","0.100.1.0"]
// 
//
// 示例 5： 
//
// 
//输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 20 
// s 仅由数字组成 
// 
// Related Topics 字符串 回溯 
// 👍 742 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses {
    public static void main(String[] args) {
        String s = "25525511135";
        new RestoreIpAddresses().new Solution().restoreIpAddresses(s);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        /**
         * 使用dfs遍历的方法，就是有很多的细节，比如提前剪枝
         * 可以使用一个temp来存储原始字符串分割的结果
         */
        List<String> res;
        List<String> temp;//使用temp来储存字符串切片的结果
        int len;
        public List<String> restoreIpAddresses(String s) {
            this.len = s.length();
            if (len<4 || len>12) return new ArrayList<>();
            res = new ArrayList<>();
            temp = new ArrayList<>();
            dfs(0, s, new StringBuilder(),0);
            return res;
        }

        private void dfs(int begin, String s) {
            if (temp.size() == 4){//说明已经达到了四片
                if (begin == len){//如果此时耗尽了字符串就说明找到了符合要求的ip
                    String s1 = temp.get(0);
                    for (int i = 1; i < 4 ; i++) {
                        s1 += '.'+ temp.get(i);
                    }
                    res.add(s1);
                }
            }else {//没有满继续找
                for (int i = 1; i <=3 ; i++) {
                    if (begin+i<len+1){//使得截取字符串时不越界
                        if (i!=1 && s.charAt(begin)=='0')return;//去除前导零
                        String substring = s.substring(begin, begin + i);//字符切片
                        //剪枝，此时只能跳回到上次递归，再多取一位也没意义了
                        if (i == 3 &&Integer.parseInt(substring)>255)return;
                        temp.add(substring);
                        dfs(begin+i, s);
                        temp.remove(temp.size()-1);
                    }
                }
            }

        }

        //二刷，使用的count进行ip段的计数，可以根据count进行剪枝，这个版本相对一刷更好理解一些
        public void dfs(int index, String s, StringBuilder ip, int count){
            if (index == s.length()&&count == 4){
                String temp = ip.toString();//TODO 这里不要对ip进行操作，否则会影响回溯结果的去除
                res.add(temp.substring(0, temp.length()-1));
            }else if (count < 4){
                for (int i = index; i < s.length(); i++){
                    if (i > index && s.charAt(index)-'0' == 0) break;//去除当前ip段的前导零，剪枝
                    String sub = s.substring(index, i+1);//这是当前ip段
                    if (Integer.parseInt(sub) >255) break;//剪枝
                    ip.append(sub).append(".");
                    dfs(i+1, s, ip,count+1);
                    ip.delete(ip.length()-(sub.length()+1),ip.length());//去除当前结果
                }
            }
        }


        /**
         * 优雅的四重遍历暴力解法
         */
        public List<String> restoreIpAddresses2(String s) {
            int len = s.length();
            if (len<3 || len>12) return new ArrayList<>();
            List<String> res = new ArrayList<>();
            for (int a = 1; a < 4; a++) {
                for (int b = 1; b < 4; b++) {
                    for (int c = 1; c < 4; c++) {
                        for (int d = 1; d < 4; d++) {
                            if (a + b + c + d == len){
                                //注意这里转Integer的时候把前导零去掉了，要判断以下拼接后的长度和原始字符串的关系
                                Integer s1 = Integer.parseInt(s.substring(0, a));
                                Integer s2 = Integer.parseInt(s.substring(a, a+b));
                                Integer s3 = Integer.parseInt(s.substring(a+b, a+b+c));
                                Integer s4 = Integer.parseInt(s.substring(a+b+c,a+b+c+d));
                                if (s1<=255&&s2<=255&&s3<=255&&s4<=255){
                                    String temp = String.valueOf(s1)+'.'+String.valueOf(s2)+'.'+
                                            String.valueOf(s3)+'.'+String.valueOf(s4);
                                    //符合要求的字符串相比于之前的字符串只多三个 '.'
                                    if (temp.length() == len+3) res.add(temp);
                                }

                            }
                        }
                    }
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

















































}